{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Adjacent Swaps to Reach the Kth Smallest Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getMinSwaps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #邻位交换的最小次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个表示大整数的字符串 <code>num</code> ，和一个整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>如果某个整数是 <code>num</code> 中各位数字的一个 <strong>排列</strong> 且它的 <strong>值大于</strong> <code>num</code> ，则称这个整数为 <strong>妙数</strong> 。可能存在很多妙数，但是只需要关注 <strong>值最小</strong> 的那些。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>num = \"5489355142\"</code> ：\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li>第 1 个最小妙数是 <code>\"5489355214\"</code></li>\n",
    "\t\t<li>第 2 个最小妙数是 <code>\"5489355241\"</code></li>\n",
    "\t\t<li>第 3 个最小妙数是 <code>\"5489355412\"</code></li>\n",
    "\t\t<li>第 4 个最小妙数是 <code>\"5489355421\"</code></li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回要得到第 <code>k</code> 个 <strong>最小妙数</strong> 需要对 <code>num</code> 执行的 <strong>相邻位数字交换的最小次数</strong> 。</p>\n",
    "\n",
    "<p>测试用例是按存在第 <code>k</code> 个最小妙数而生成的。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>num = \"5489355142\", k = 4\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>第 4 个最小妙数是 \"5489355421\" ，要想得到这个数字：\n",
    "- 交换下标 7 和下标 8 对应的位：\"5489355<strong>14</strong>2\" -&gt; \"5489355<strong>41</strong>2\"\n",
    "- 交换下标 8 和下标 9 对应的位：\"54893554<strong>12</strong>\" -&gt; \"54893554<strong>21</strong>\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>num = \"11112\", k = 4\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>第 4 个最小妙数是 \"21111\" ，要想得到这个数字：\n",
    "- 交换下标 3 和下标 4 对应的位：\"111<strong>12</strong>\" -&gt; \"111<strong>21</strong>\"\n",
    "- 交换下标 2 和下标 3 对应的位：\"11<strong>12</strong>1\" -&gt; \"11<strong>21</strong>1\"\n",
    "- 交换下标 1 和下标 2 对应的位：\"1<strong>12</strong>11\" -&gt; \"1<strong>21</strong>11\"\n",
    "- 交换下标 0 和下标 1 对应的位：\"<strong>12</strong>111\" -&gt; \"<strong>21</strong>111\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>num = \"00123\", k = 1\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>第 1 个最小妙数是 \"00132\" ，要想得到这个数字：\n",
    "- 交换下标 3 和下标 4 对应的位：\"001<strong>23</strong>\" -&gt; \"001<strong>32</strong>\"\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= num.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 1000</code></li>\n",
    "\t<li><code>num</code> 仅由数字组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-adjacent-swaps-to-reach-the-kth-smallest-number](https://leetcode.cn/problems/minimum-adjacent-swaps-to-reach-the-kth-smallest-number/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-adjacent-swaps-to-reach-the-kth-smallest-number](https://leetcode.cn/problems/minimum-adjacent-swaps-to-reach-the-kth-smallest-number/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"5489355142\"\\n4', '\"11112\"\\n4', '\"00123\"\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinSwaps(self, num: str, k: int) -> int:\n",
    "\n",
    "        def findnext_nums(nums):\n",
    "            for i in range(n-1,0,-1):\n",
    "                if nums[i-1] < nums[i]:   #找到后面数字比前面数字大的情况，不加这行会导致超时，具体情况可以试试\n",
    "                    for j in range(n-1,i-1,-1):   #从后往前遍历到索引i-1的前面\n",
    "                        if nums[i-1] < nums[j]:   #从后往前找到数字比nums[i-1]大的数字\n",
    "                            nums[i-1],nums[j] = nums[j],nums[i-1]    #交换这两个数字\n",
    "                            nums[i:] = sorted(nums[i:])       #将i-1之后的数子排序，因为这样才是最小妙数\n",
    "                            return nums\n",
    "\n",
    "        n = len(num); nums = list(num); num = list(num)\n",
    "        for _ in range(k):\n",
    "            nums = findnext_nums(nums)\n",
    "        \n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] != num[i]:\n",
    "                for j in range(i+1,n):\n",
    "                    if nums[i] == num[j]:\n",
    "                        cnt += j - i\n",
    "                        num[i+1:j+1] = num[i:j]\n",
    "                        break\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinSwaps(self, num: str, k: int) -> int:\n",
    "        cnt = 0\n",
    "        num = list(num)\n",
    "        row_num = [i for i in num]\n",
    "        for i in range(k):\n",
    "            self.next_max(num)\n",
    "        for i in range(len(num)):\n",
    "            if num[i] == row_num[i]:\n",
    "                continue\n",
    "            for j in range(i + 1, len(num)):\n",
    "                if row_num[j] == num[i]:\n",
    "                    for k in range(j, i, -1):\n",
    "                        row_num[k], row_num[k - 1] = row_num[k - 1], row_num[k]\n",
    "                        cnt += 1\n",
    "                    break\n",
    "        return cnt\n",
    "\n",
    "\n",
    "    def next_max(self, nums):\n",
    "        for i in range(len(nums) - 1, 0, -1):\n",
    "            if nums[i] > nums[i - 1]:\n",
    "                a = i - 1\n",
    "                break\n",
    "        else:\n",
    "            nums.sort()\n",
    "            return\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            if nums[i] > nums[a]:\n",
    "                b = i\n",
    "                break\n",
    "        nums[a], nums[b] = nums[b], nums[a]\n",
    "        nums[a + 1:] = sorted(nums[a + 1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinSwaps(self, num: str, k: int) -> int:\n",
    "        def NextPermutation(num_k: List[str]):\n",
    "            n = len(num_k)\n",
    "            i, j = n - 2, n - 1\n",
    "            while i >= 0 and num_k[i] >= num_k[i+1]:\n",
    "                i -= 1\n",
    "            if i >= 0:\n",
    "                while j >= i and num_k[i] >= num_k[j]:\n",
    "                    j -= 1\n",
    "                num_k[i], num_k[j] = num_k[j], num_k[i]\n",
    "            \n",
    "            left, right = i + 1, n - 1\n",
    "            while left < right:\n",
    "                num_k[left], num_k[right] = num_k[right], num_k[left]\n",
    "                left += 1\n",
    "                right -= 1\n",
    "        \n",
    "        num = list(num)\n",
    "        num_n = num[:]\n",
    "        for i in range(k):\n",
    "            NextPermutation(num_n)\n",
    "        \n",
    "        i = 0\n",
    "        ans = 0\n",
    "        while i < len(num):\n",
    "            if num[i] != num_n[i]:\n",
    "                j = i + 1\n",
    "                while j < len(num):\n",
    "                    if num[j] == num_n[i]:\n",
    "                        while j > i:\n",
    "                            ans += 1\n",
    "                            num[j-1], num[j] = num[j], num[j-1]\n",
    "                            j -= 1\n",
    "                        break\n",
    "                    j += 1\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getMinSwaps(self, num: str, k: int) -> int:\r\n",
    "\r\n",
    "        lis1 = list(num)\r\n",
    "        lis2 = list(num)\r\n",
    "\r\n",
    "        def nex_num(arr):\r\n",
    "            n = len(arr)\r\n",
    "            left = -1\r\n",
    "            right = -1\r\n",
    "            for i in range(n - 1, 0, -1):\r\n",
    "                if arr[i] > arr[i - 1]:\r\n",
    "                    left = i - 1\r\n",
    "                    break\r\n",
    "            \r\n",
    "            for i in range(n - 1, left, -1):\r\n",
    "                if arr[i] > arr[left]:\r\n",
    "                    arr[i], arr[left] = arr[left], arr[i]\r\n",
    "                    break\r\n",
    "            arr[left+1:] = arr[:left:-1]\r\n",
    "            return(arr)\r\n",
    "        \r\n",
    "        for i in range(k):\r\n",
    "            lis2 = nex_num(lis2)\r\n",
    "\r\n",
    "        def get_num(lis1, lis2):\r\n",
    "            n = len(lis1)\r\n",
    "            res = 0\r\n",
    "            for i in range(n):\r\n",
    "                if lis1[i] != lis2[i]:\r\n",
    "                    j = i + 1\r\n",
    "                    while(lis1[j] != lis2[i]):\r\n",
    "                        j += 1\r\n",
    "                    lis1[i + 1:j + 1] = lis1[i:j]\r\n",
    "                    lis1[i] = lis2[i]\r\n",
    "                    res += (j - i)\r\n",
    "\r\n",
    "            return(res)\r\n",
    "\r\n",
    "        return(get_num(lis1, lis2))\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinSwaps(self, num: str, k: int) -> int:\n",
    "        lst = list(num)\n",
    "        # 首先模拟找到第k小的妙数，从后往前遍历将第一个较小的数字换成后面比它大但最小的数字，交换后对其后面的直接排序\n",
    "        n = len(lst)\n",
    "        while k:\n",
    "            p = n - 1\n",
    "            for j in range(n - 2, -1, -1):\n",
    "                if lst[p] > lst[j]:\n",
    "                    # 存在比它大的\n",
    "                    for i in range(j + 1, n):\n",
    "                        # 比它大里面找较小的\n",
    "                        if lst[j] < lst[i] < lst[p]:\n",
    "                            p = i\n",
    "                    break\n",
    "                else:\n",
    "                    p = j\n",
    "            lst[j], lst[p] = lst[p], lst[j]\n",
    "            lst[j + 1:] = sorted(lst[j + 1:])\n",
    "            k -= 1\n",
    "\n",
    "        # 再利用冒泡思想贪心进行交换计算次数\n",
    "        ans = 0\n",
    "        original = list(num)\n",
    "        for i in range(n):\n",
    "            if original[i] != lst[i]:\n",
    "                for j in range(i + 1, n):\n",
    "                    # 用最近的位置冒泡交换当前不等的值\n",
    "                    if original[j] == lst[i]:\n",
    "                        ans += j - i\n",
    "                        original.insert(i, original.pop(j))\n",
    "                        break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinSwaps(self, num: str, k: int) -> int:\n",
    "        lis = list(num)\n",
    "        n = len(num)\n",
    "        for _ in range(k):\n",
    "            x = n - 2\n",
    "            while lis[x] >= lis[x+1]:\n",
    "                x -= 1\n",
    "            l, r, jd = x + 1, n - 1, lis[x]\n",
    "            while l < r:\n",
    "                mid = (l+r+1)//2\n",
    "                if lis[mid] > jd:\n",
    "                    l = mid\n",
    "                else: r = mid - 1\n",
    "            lis[x], lis[l] = lis[l], lis[x]\n",
    "            lis[x+1:] = sorted(lis[x+1:])\n",
    "        dc, jdlis = defaultdict(list), [i&(-i) for i in range(n+1)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            dc[lis[i]].append(i)\n",
    "        res = 0\n",
    "        for i in num:\n",
    "            inx = dc[i].pop() + 1\n",
    "            pinx = inx\n",
    "            while pinx:\n",
    "                res += jdlis[pinx]\n",
    "                pinx = pinx & (pinx - 1)\n",
    "            while inx <= n:\n",
    "                jdlis[inx] -= 1\n",
    "                inx += inx&(-inx)\n",
    "        return res - n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinSwaps(self, num: str, k: int) -> int:\n",
    "\n",
    "        def findnext_nums(nums):\n",
    "            for i in range(n-1, 0, -1):\n",
    "                if nums[i-1] < nums[i]:\n",
    "                    for j in range(n-1, i-1, -1):\n",
    "                        if nums[i-1] < nums[j]:\n",
    "                            nums[i-1], nums[j] = nums[j], nums[i-1] \n",
    "                            nums[i:] = sorted(nums[i:])\n",
    "                            return nums\n",
    "\n",
    "        n = len(num)\n",
    "        num = list(num)\n",
    "        numk = num[:]\n",
    "        for _ in range(k):\n",
    "            numk = findnext_nums(numk)\n",
    "\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if num[i] != numk[i]:\n",
    "                for j in range(i+1,n):\n",
    "                    if num[j] == numk[i]:\n",
    "                        cnt += j-i\n",
    "                        num[i+1:j+1] = num[i:j]\n",
    "                        break\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinSwaps(self, num: str, k: int) -> int:\n",
    "        #i = len(num)-2\n",
    "        def next_perm(nums):\n",
    "            nums = nums[:]\n",
    "            i = len(nums)-2\n",
    "            while i>=0 and nums[i]>=nums[i+1]:\n",
    "                i -= 1\n",
    "            \n",
    "            if i>=0:\n",
    "                j = len(nums)-1\n",
    "                while j >=0 and nums[i]>=nums[j]:\n",
    "                    j -= 1\n",
    "                \n",
    "                nums[i],nums[j]=nums[j],nums[i]\n",
    "                l,r = i+1,len(nums)-1\n",
    "                while l<r:\n",
    "                    nums[l],nums[r]=nums[r],nums[l]\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "            return nums\n",
    "        \n",
    "        next_nums = nums=list(num)\n",
    "        for i in range(k):\n",
    "            next_nums = next_perm(next_nums)\n",
    "        #print(next_nums)\n",
    "        #print(nums)\n",
    "        \n",
    "        n = len(next_nums)\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            if nums[i]!=next_nums[i]:\n",
    "                for j in range(i+1,n):\n",
    "                    if nums[j]==next_nums[i]:\n",
    "                        for k in range(j-1,i-1,-1):\n",
    "                            ans += 1\n",
    "                            nums[k],nums[k+1]=nums[k+1],nums[k]\n",
    "                        break\n",
    "        return ans\n",
    "                    \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinSwaps(self, num: str, k: int) -> int:\n",
    "        def nextPermutation(nums: List[int]) -> None:\n",
    "            n = len(nums)\n",
    "            i = n - 2\n",
    "            while i >= 0 and nums[i] >= nums[i + 1]:\n",
    "                i -= 1\n",
    "            if i >= 0 :\n",
    "                j = n - 1\n",
    "                while j >= 0 and nums[i] >= nums[j]:\n",
    "                    j -= 1\n",
    "                nums[i], nums[j] = nums[j] , nums[i]\n",
    "            \n",
    "            left, right = i + 1, n - 1\n",
    "            while left < right:\n",
    "                nums[left], nums[right] = nums[right], nums[left]\n",
    "                left += 1\n",
    "                right -= 1\n",
    "        \n",
    "        num = list(num)\n",
    "        num_k = num[:]\n",
    "        for _ in range(k):\n",
    "            nextPermutation(num_k)\n",
    "        \n",
    "        n = len(num)\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            if num[i] != num_k[i]:\n",
    "                for j in range(i + 1, n):\n",
    "                    if num[j] == num_k[i]:\n",
    "                        for p in range(j - 1, i - 1, -1):\n",
    "                            ans += 1\n",
    "                            num[p], num[p + 1] = num[p + 1], num[p]\n",
    "                        break\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getMinSwaps(self, num: str, k: int) -> int:\r\n",
    "\r\n",
    "        lis1 = list(num)\r\n",
    "        lis2 = list(num)\r\n",
    "\r\n",
    "        def nex_num(arr):\r\n",
    "            n = len(arr)\r\n",
    "            left = -1\r\n",
    "            right = -1\r\n",
    "            for i in range(n - 1, 0, -1):\r\n",
    "                if arr[i] > arr[i - 1]:\r\n",
    "                    left = i - 1\r\n",
    "                    break\r\n",
    "            \r\n",
    "            for i in range(n - 1, left, -1):\r\n",
    "                if arr[i] > arr[left]:\r\n",
    "                    arr[i], arr[left] = arr[left], arr[i]\r\n",
    "                    break\r\n",
    "            arr[left+1:] = arr[:left:-1]\r\n",
    "            return(arr)\r\n",
    "        \r\n",
    "        for i in range(k):\r\n",
    "            lis2 = nex_num(lis2)\r\n",
    "\r\n",
    "        def get_num(lis1, lis2):\r\n",
    "            n = len(lis1)\r\n",
    "            res = 0\r\n",
    "            for i in range(n):\r\n",
    "                if lis1[i] != lis2[i]:\r\n",
    "                    j = i + 1\r\n",
    "                    while(lis1[j] != lis2[i]):\r\n",
    "                        j += 1\r\n",
    "                    lis1[i + 1:j + 1] = lis1[i:j]\r\n",
    "                    lis1[i] = lis2[i]\r\n",
    "                    res += (j - i)\r\n",
    "\r\n",
    "            return(res)\r\n",
    "\r\n",
    "        return(get_num(lis1, lis2))\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getMinSwaps(self, num: str, k: int) -> int:\r\n",
    "\r\n",
    "        lis1 = list(num)\r\n",
    "        lis2 = list(num)\r\n",
    "\r\n",
    "        def nex_num(arr):\r\n",
    "            n = len(arr)\r\n",
    "            left = -1\r\n",
    "            right = -1\r\n",
    "            for i in range(n - 1, 0, -1):\r\n",
    "                if arr[i] > arr[i - 1]:\r\n",
    "                    left = i - 1\r\n",
    "                    break\r\n",
    "            \r\n",
    "            for i in range(n - 1, left, -1):\r\n",
    "                if arr[i] > arr[left]:\r\n",
    "                    arr[i], arr[left] = arr[left], arr[i]\r\n",
    "                    break\r\n",
    "            arr[left+1:] = arr[:left:-1]\r\n",
    "            return(arr)\r\n",
    "        \r\n",
    "        for i in range(k):\r\n",
    "            lis2 = nex_num(lis2)\r\n",
    "\r\n",
    "        def get_num(lis1, lis2):\r\n",
    "            n = len(lis1)\r\n",
    "            res = 0\r\n",
    "            for i in range(n):\r\n",
    "                if lis1[i] != lis2[i]:\r\n",
    "                    j = i + 1\r\n",
    "                    while(lis1[j] != lis2[i]):\r\n",
    "                        j += 1\r\n",
    "                    lis1[i + 1:j + 1] = lis1[i:j]\r\n",
    "                    lis1[i] = lis2[i]\r\n",
    "                    res += (j - i)\r\n",
    "\r\n",
    "            return(res)\r\n",
    "\r\n",
    "        return(get_num(lis1, lis2))\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def nextPermutation(nums: List[int]) -> None:\n",
    "    i = len(nums) - 2\n",
    "    while i >= 0 and nums[i] >= nums[i + 1]:\n",
    "        i -= 1\n",
    "    if i >= 0:\n",
    "        j = len(nums) - 1\n",
    "        while j >= 0 and nums[i] >= nums[j]:\n",
    "            j -= 1\n",
    "        nums[i], nums[j] = nums[j], nums[i]\n",
    "    \n",
    "    left, right = i + 1, len(nums) - 1\n",
    "    while left < right:\n",
    "        nums[left], nums[right] = nums[right], nums[left]\n",
    "        left += 1\n",
    "        right -= 1\n",
    "class BIT1:\n",
    "    \"\"\"单点修改,区间和查询\"\"\"\n",
    "\n",
    "    __slots__ = \"size\", \"bit\", \"tree\"\n",
    "\n",
    "    def __init__(self, n: int):\n",
    "        self.size = n\n",
    "        self.bit = n.bit_length()\n",
    "        self.tree = [0]*(n+1)\n",
    "\n",
    "    def add(self, index: int, delta: int) -> None:\n",
    "        # index 必须大于0\n",
    "        while index <= self.size:\n",
    "            self.tree[index]+=delta\n",
    "            index += index & -index\n",
    "\n",
    "    def _query(self, index: int) -> int: \n",
    "        res = 0\n",
    "        while index > 0:\n",
    "            res += self.tree[index]\n",
    "            index -= index & -index\n",
    "        return res\n",
    "\n",
    "    def query(self, left: int, right: int) -> int:\n",
    "        return self._query(right) - self._query(left - 1)\n",
    "class Solution:\n",
    "    def getMinSwaps(self, num: str, k: int) -> int:\n",
    "        n=len(num)\n",
    "        arr=[int(i) for i in num]\n",
    "        brr=arr[:]\n",
    "        for _ in range(k):\n",
    "            nextPermutation(brr)\n",
    "        idx=defaultdict(list)\n",
    "        for i,b in enumerate(brr,2):\n",
    "            idx[b].append(i)\n",
    "        cnt=defaultdict(int)\n",
    "        al=[]\n",
    "        for a in arr:\n",
    "            al.append(idx[a][cnt[a]])\n",
    "            cnt[a]+=1\n",
    "        bit=BIT1(n+10)\n",
    "        res=0\n",
    "        for i in al:\n",
    "            res+=bit.query(i+1,n+5)\n",
    "            bit.add(i,1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinSwaps(self, num: str, k: int) -> int:\n",
    "        s = list(num)\n",
    "        n = len(s)\n",
    "        tmp = s.copy()\n",
    "        def next_permutation():\n",
    "            i = len(s) - 2\n",
    "            while i >= 0 and s[i] >= s[i+1]:\n",
    "                i -= 1\n",
    "            j = len(s) - 1\n",
    "            while s[j] <= s[i]:\n",
    "                j -= 1\n",
    "            s[i], s[j] = s[j], s[i]\n",
    "            s[i+1:] = s[i+1:][::-1]\n",
    "        while k:\n",
    "            k -= 1\n",
    "            next_permutation()\n",
    "        ret = 0\n",
    "        print(tmp, s)\n",
    "        for i in range(n):\n",
    "            if s[i] != tmp[i]:\n",
    "                for j in range(i + 1, n):\n",
    "                    if s[i] == tmp[j]:\n",
    "                        ret += j - i\n",
    "                        for k in range(j, i, -1):\n",
    "                            tmp[k] = tmp[k - 1]\n",
    "                        tmp[i] = tmp[j]\n",
    "                        break\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinSwaps(self, num: str, k: int) -> int:\n",
    "        targetStr= num[:]\n",
    "        for _ in range(k):\n",
    "            targetStr = self.get_next_permutation(targetStr)\n",
    "        #print(targetStr)\n",
    "        n = len(num)\n",
    "        mapidx = [0 for _ in range(n)]      #数字的映射关系\n",
    "        digit_cnt = [0 for _ in range(10)]  #当前是几个了。方便确定映射关系的\n",
    "        for i in range(n):\n",
    "            x = int(num[i])\n",
    "            digit_cnt[x] += 1\n",
    "            y = digit_cnt[x]\n",
    "            for j in range(n):\n",
    "                if targetStr[j] == num[i]:\n",
    "                    y -= 1\n",
    "                    if y == 0:\n",
    "                        mapidx[i] = j\n",
    "                        break\n",
    "        reverse = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if (mapidx[i] > mapidx[j]):\n",
    "                    reverse += 1\n",
    "        return reverse\n",
    "\n",
    "    def get_next_permutation(self, nums: str) -> str:\n",
    "        nums = list(nums)\n",
    "        n = len(nums)\n",
    "        if n < 2:\n",
    "            return    \n",
    "        i = n - 1\n",
    "        while i > 0 and nums[i-1] >= nums[i]:\n",
    "            i -= 1\n",
    "        L = i\n",
    "        R = n - 1\n",
    "        while L < R:\n",
    "            nums[L], nums[R] = nums[R], nums[L]\n",
    "            L += 1\n",
    "            R -= 1\n",
    "        if i != 0:\n",
    "            for j in range(i, n):\n",
    "                if nums[j] > nums[i - 1]:\n",
    "                    nums[i-1], nums[j] = nums[j], nums[i-1]\n",
    "                    break\n",
    "        return ''.join(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinSwaps(self, num_str: str, k: int) -> int:\n",
    "        num = list(num_str)\n",
    "        target = num[:]\n",
    "        n = len(num)\n",
    "\n",
    "        def nxt_per():\n",
    "            i = n - 2\n",
    "            while i >= 0 and target[i] >= target[i + 1]:\n",
    "                i -= 1\n",
    "            if i >= 0:\n",
    "                j = n - 1\n",
    "                while j >= 0 and target[i] >= target[j]:\n",
    "                    j -= 1\n",
    "                target[i], target[j] = target[j], target[i]\n",
    "            l = i + 1\n",
    "            r = n - 1\n",
    "            while l < r:\n",
    "                target[l], target[r] = target[r], target[l]\n",
    "                l += 1\n",
    "                r -= 1\n",
    "        \n",
    "        for i in range(k):\n",
    "            nxt_per()\n",
    "        ans = 0\n",
    "        print(target)\n",
    "        for i, x in enumerate(num):\n",
    "            if x != target[i]:\n",
    "                for j in range(i + 1, n):\n",
    "                    if x == target[j]:\n",
    "                        # i和j 逐位交换\n",
    "                        for k in range(j, i, -1):\n",
    "                            ans += 1\n",
    "                            target[k], target[k - 1] = target[k - 1], target[k]\n",
    "                        break\n",
    "        return ans\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
